package Top_Interview_Questions.Sort;

import Top_Interview_Questions.Sort.Supple.ListNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/22 14:53
 * <p>
 * 解析:
 * https://leetcode-cn.com/problems/sort-list/solution
 * /sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
 *
 * #.点掌握归并排序+快慢指针找中点
 * #.此题的非递归法还没有看
 *
 */
public class _0148 {

    public static void main(String[] args) {
        _0148 test = new _0148();

        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(6);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(1);
        ListNode node7 = new ListNode(7);
        ListNode node8 = new ListNode(8);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;
        node8.next = null;

        test.sortList2(node1);

    }

    /*--------------------------------------非递归归并排序法---------------------------------*/
    public ListNode sortList3(ListNode head) {
        ListNode h, h1, h2, pre, res;
        h = head;
        int length = 0, intv = 1;
        while (h != null) {
            h = h.next;
            length++;
        }
        res = new ListNode(0);
        res.next = head;
        while (intv < length) {
            pre = res;
            h = res.next;
            while (h != null) {
                int i = intv;
                h1 = h;
                while (i > 0 && h != null) {
                    h = h.next;
                    i--;
                }
                if (i > 0) break;
                i = intv;
                h2 = h;
                while (i > 0 && h != null) {
                    h = h.next;
                    i--;
                }
                int c1 = intv, c2 = intv - i;
                while (c1 > 0 && c2 > 0) {
                    if (h1.val < h2.val) {
                        pre.next = h1;
                        h1 = h1.next;
                        c1--;
                    } else {
                        pre.next = h2;
                        h2 = h2.next;
                        c2--;
                    }
                    pre = pre.next;
                }
                pre.next = c1 == 0 ? h2 : h1;
                while (c1 > 0 || c2 > 0) {
                    pre = pre.next;
                    c1--;
                    c2--;
                }
                pre.next = h;
            }
            intv *= 2;
        }
        return res.next;
    }
    /*------------------------------------------------------------------------------------*/

    /*---------------------------------------递归归并排序法---------------------------------*/

    /**
     * 1.为什么要在循环里加呢?因为要循环构造新链表啊
     * 2.debug看一下就都明白了。
     */
    public ListNode sortList2(ListNode head) {
        if (head == null || head.next == null)
            return head;
        //快慢指针找中点,核心就是快指针的步伐是慢指针的两倍,当快指针到终点时,满指针刚好到一半。
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList2(head);
        ListNode right = sortList2(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            //1.
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }
    /*-----------------------------------------------------------------------------------*/


    /*---------------------------------------自己写的方法----------------------------------*/
    //调Java-Api,打败%22
    public ListNode sortList1(ListNode head) {
        if (head == null) {
            return null;
        }

        List<Integer> list = new ArrayList<>();

        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        Collections.sort(list);

        ListNode first = new ListNode(0);
        ListNode cur = first;
        for (Integer k : list) {
            ListNode node = new ListNode(k);
            cur.next = node;
            cur = cur.next;
        }
        first = first.next;
        return first;
    }
    /*------------------------------------------------------------------------------------*/
}
